package com.company.algo.stack.monotonicStack;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * https://leetcode-cn.com/problems/trapping-rain-water/
 */
public class TrappingRainWater {
    //1.暴力解法
    public int trap(int[] height) {
        int n = height.length;
        int res = 0;
        for (int i = 0; i < n; i++) {
            int l_max = 0, r_max = 0;
            //找左边最高的柱子
            for (int j = i-1; j >= 0 ; j--) {
                if (height[j]>l_max) l_max = height[j];
            }
            //找右边最高的柱子
            for (int j = i+1; j < n; j++) {
                if (height[j]>r_max) r_max=height[j];
            }

            //如果自己就是最高，则可以接到的雨水为0
            int h = Math.min(l_max,r_max)-height[i];
            res += Math.max(h, 0);
        }
        return res;
    }

    /**
     * 2.备忘录优化
     * 之前的暴力解法，不是在每个位置i都要计算r_max和l_max吗？
     * 我们直接把结果都提前计算出来，别傻不拉几的每次都遍历，这时间复杂度不就降下来了嘛。
     * 我们开两个数组r_max和l_max充当备忘录，
     * l_max[i]表示位置i左边最高的柱子高度，
     * r_max[i]表示位置i右边最高的柱子高度。
     * 预先把这两个数组计算好，避免重复计算：
     */
    public int trap2(int[] height) {
        if (height.length == 0) return 0;
        int n = height.length;
        int res = 0;
        //数组充当备忘录
        int[] l_max = new int[n];
        int[] r_max = new int[n];
        //初始化
        l_max[0] = height[0];
        r_max[n-1] = height[n-1];
        // 从左向右计算 l_max
        for (int i = 1; i < n; i++) {
            l_max[i] = Math.max(height[i],l_max[i-1]);
        }
        // 从右向左计算r_max
        for (int i = n-2; i >= 0; i--) {
            r_max[i] = Math.max(height[i],r_max[i+1]);
        }
        // 计算答案
        for (int i = 1; i < n-1; i++) {
            res += Math.min(l_max[i], r_max[i]) - height[i];
        }
        return res;
    }

    /**https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247487733&idx=1&sn=f27307be00bdbbbcf9bee4c46e793f83&scene=21#wechat_redirect
     * 3.双指针解法
     *这种解法的思路是完全相同的，但在实现手法上非常巧妙，
     * 我们这次也不要用备忘录提前计算了，而是用双指针边走边算，节省下空间复杂度。
     * 定理一：在某个位置i处，它能存的水，取决于它左右两边的最大值中较小的一个。
     * 定理二：当我们从左往右处理到left下标时，左边的最大值left_max对它而言是可信的，
     * 但right_max对它而言是不可信的。（见下图，由于中间状况未知，对于left下标而言，right_max未必就是它右边最大的值）
     * 定理三：当我们从右往左处理到right下标时，右边的最大值right_max对它而言是可信的，但left_max对它而言是不可信的。
     *                                    right_max
     *  left_max                             __
     *    __                                |  |
     *   |  |__   __??????????????????????  |  |
     * __|     |__|                       __|  |__
     *         left                      right
     * 对于位置left而言，它左边最大值一定是left_max，右边最大值“大于等于”right_max，这时候，如果left_max<right_max成立，
     * 那么它就知道自己能存多少水了。无论右边将来会不会出现更大的right_max，都不影响这个结果。
     * 所以当left_max<right_max时，我们就希望去处理left下标，反之，我们希望去处理right下标。
     */
    public int trap3(int[] height) {
        int n = height.length;
        int left = 0, right = n - 1;
        int res = 0;
        int l_max = height[0];
        int r_max = height[n-1];
        while (left <= right){
            l_max = Math.max(l_max,height[left]);
            r_max = Math.max(r_max,height[right]);
            // res += min(l_max, r_max) - height[i]
            if (l_max < r_max){
                res += l_max - height[left];
                left++;
            }else {
                res += r_max - height[right];
                right--;
            }
        }
        return res;
    }

    /**https://leetcode-cn.com/problems/trapping-rain-water/solution/42-jie-yu-shui-shuang-zhi-zhen-dong-tai-wguic/
     * 4，单调栈解法
     *  （1）首先单调栈是按照行方向来计算雨水
     *  （2）使用单调栈内元素的顺序
     *  从栈头（元素从栈头弹出）到栈底的顺序应该是从小到大的顺序。
     *  因为一旦发现添加的柱子高度大于栈头元素了，此时就出现凹槽了，栈头元素就是凹槽底部的柱子，
     *  栈头第二个元素就是凹槽左边的柱子，而添加的元素就是凹槽右边的柱子
     *  （3）遇到相同高度的柱子怎么办。
     *  遇到相同的元素，更新栈内下标，就是将栈里元素（旧下标）弹出，将新元素（新下标）加入栈中。
     *  例如 5 5 1 3 这种情况。如果添加第二个5的时候就应该将第一个5的下标弹出，把第二个5添加到栈中。
     *  因为我们要求宽度的时候 如果遇到相同高度的柱子，需要使用最右边的柱子来计算宽度。
     *  (4) 栈里要保存什么数值
     *  是用单调栈，其实是通过 长 * 宽 来计算雨水面积的。
     * 长就是通过柱子的高度来计算，宽是通过柱子之间的下标来计算，
     * 那么栈里有没有必要存一个pair<int, int>类型的元素，保存柱子的高度和下标呢。
     * 其实不用，栈里就存放int类型的元素就行了，表示下标，想要知道对应的高度，通过height[stack.top()] 就知道弹出的下标对应的高度了。
     */
    public int trap4(int[] height) {
        if (height.length<=2) return 0;
        Deque<Integer> st = new LinkedList<>();
        st.push(0);
        int res = 0;
        for (int i = 1; i < height.length; i++) {
            if (height[i]<height[st.peek()]){
                st.push(i);
            }else if (height[i] == height[st.peek()]){
                st.poll();
                st.push(i);
            }else {
                while (!st.isEmpty() && height[i]>height[st.peek()]){
                    int base = st.poll();
                    if (!st.isEmpty()){
                        int h = Math.min(height[st.peek()],height[i])-height[base];
                        int w = i-st.peek()-1;
                        res += h * w;
                    }
                }
                st.addLast(i);
            }
        }
        return res;
    }




    public static void main(String[] args) {
        TrappingRainWater Main = new TrappingRainWater();
        int[] height = {2,5,3,2,4};
        System.out.println(Main.trap4(height));
    }


}
